#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
class Solution
{
public:
    /**
     * @brief 思路-寻找一个数的质因数
     *
     * @param target 1 <= target <= 10^5
     * @return vector<vector<int>>
     */
    vector<vector<int>> findContinuousSequence_0(int target)
    {
        vector<vector<int>> ans;
        for (size_t i = 3; i < log(target); i++)
        {
            if (!(target % i))
            {
                // get i
            }
        }
    }

    vector<vector<int>> findContinuousSequence(int target)
    {
        vector<vector<int>> vec;
        vector<int> res;
        // (target - 1) / 2 等效于 target / 2 下取整
        int sum = 0, limit = (target - 1) / 2;
        for (int i = 1; i <= limit; ++i)
        {
            for (int j = i;; ++j)
            {
                sum += j;
                if (sum > target)
                {
                    sum = 0;
                    break;
                }
                else if (sum == target)
                {
                    res.clear();
                    for (int k = i; k <= j; ++k)
                    {
                        res.emplace_back(k);
                    }
                    vec.emplace_back(res);
                    sum = 0;
                    break;
                }
            }
        }
        return vec;
    }

    /**
     * @brief
     *
     * @param target
     * @return vector<vector<int>>
     */
    vector<vector<int>> findContinuousSequence_2(int target)
    {
        vector<vector<int>> vec;
        vector<int> res;
        int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
        for (int x = 1; x <= limit; ++x)
        {
            long long delta = 1 - 4 * (x - 1ll * x * x - 2 * target);
            if (delta < 0)
            {
                continue;
            }
            int delta_sqrt = (int)sqrt(delta + 0.5);
            if (1ll * delta_sqrt * delta_sqrt == delta && (delta_sqrt - 1) % 2 == 0)
            {
                int y = (-1 + delta_sqrt) / 2; // 另一个解(-1-delta_sqrt)/2必然小于0，不用考虑
                if (x < y)
                {
                    res.clear();
                    for (int i = x; i <= y; ++i)
                    {
                        res.emplace_back(i);
                    }
                    vec.emplace_back(res);
                }
            }
        }
        return vec;
    }

    vector<vector<int>> findContinuousSequence_3(int target)
    {
        vector<vector<int>> vec;
        vector<int> res;
        for (int l = 1, r = 2; l < r;)
        {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target)
            {
                res.clear();
                for (int i = l; i <= r; ++i)
                {
                    res.emplace_back(i);
                }
                vec.emplace_back(res);
                l++;
            }
            else if (sum < target)
            {
                r++;
            }
            else
            {
                l++;
            }
        }
        return vec;
    }

    /**
     * @brief 连续数字和规律
     * 
     * @param target 
     * @return vector<vector<int>> 
     */
    vector<vector<int>> findContinuousSequence_5(int target)
    {
        vector<vector<int>> res;
        int i = 1;
        while (target > 0)
        {
            target -= i++;
            if (target > 0 && target % i == 0)
            {
                vector<int> tmp;
                for (int j = 0; j < i; j++)
                    tmp.push_back(target / i + j);
                res.push_back(tmp);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }

    /**
     * @brief 数学剪枝
     *
     * @param target
     * @return vector<vector<int>>
     */
    vector<vector<int>> findContinuousSequence(int target)
    {
        int t = sqrt(target * 2) + 1;
        vector<vector<int>> res;
        for (int len = t; len >= 2; --len)
        {
            if ((target * 2) % len == 0)
            { //第一个减枝
                int tmp = target * 2 / len - len + 1;
                if (tmp > 0 && tmp % 2 == 0)
                {                    // 第二个减枝
                    int a = tmp / 2; // a为首项
                    vector<int> cur;
                    for (int i = 0; i < len; ++i)
                    {
                        cur.push_back(i + a);
                    }
                    res.push_back(cur);
                }
            }
        }
        return res;
    }
};
int main()
{
    Solution s;
    int target = 10;
    vector<vector<int>> ans = s.findContinuousSequence(target);
    for (auto &row : ans)
    {
        for (auto &v : row)
        {
            cout << v << " ";
        }
        cout << endl;
    }
    return 0;
}